package leetcode101.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Synhard
 * @version 1.0
 * @class Code28
 * @description 653. 两数之和 IV - 输入 BST
 * 给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
 *
 * 案例 1:
 *
 * 输入:
 *     5
 *    / \
 *   3   6
 *  / \   \
 * 2   4   7
 *
 * Target = 9
 *
 * 输出: True
 *
 * 案例 2:
 *
 * 输入:
 *     5
 *    / \
 *   3   6
 *  / \   \
 * 2   4   7
 *
 * Target = 28
 *
 * 输出: False
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-06-29 8:48
 */
public class Code28 {
    public static void main(String[] args) {

    }

    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        dfs(root, list);
        int i = 0, j = list.size() - 1;
        while (i != j) {
            int temp = list.get(i) + list.get(j);
            if (temp < k) {
                i++;
            } else if (temp > k) {
                j--;
            } else {
                return true;
            }
        }
        return false;
    }

    private void dfs(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        dfs(root.left, list);
        list.add(root.val);
        dfs(root.right, list);
    }
}
/*
将中序遍历结果存储在集合中然后用双指针进行判断
 */